package algorithm.math;

import util.NumberUtil;

/**
 * 预估难度: Easy
 * 两个大数相加
 * 大数相加思路，就是简单的从低位到高位,按位相加,注意进位即可
 *
 * @Author Antony
 * @Since 2018/6/25 10:41
 */
public class BigNumberAdd {

    public static void main(String[] args) {
        String aNum = "999";
        String bNum = "9999";
        System.out.println(bigNumberAdd(aNum, bNum));
    }



    /**
     * 无符号大数相加
     *
     * 难点: char转int，int转char
     *
     * 注意的点:
     * 1，结果数组要比俩字符最大长度+1
     * 2，每次计算完成后，如果没有进位，需要给进位标识置为false
     * 3，再最后结果处，如果有进位，记得要前面补1
     */
    public static String bigNumberAdd(String number_1, String number_2){
        if(number_1 == null && number_2 == null){
            throw new IllegalArgumentException("math is null!");
        }


        char[] num_1_arr = number_1.toCharArray();
        char[] num_2_arr = number_2.toCharArray();

        int i = num_1_arr.length -1;
        int j = num_2_arr.length -1;

        int result_size = i>j ? i+2 : j+2;
        char result_arr[] = new char[result_size];
        int index = result_arr.length - 1;
        //构建结果数组

        boolean carry_flag = false;  //进位标识
        int a,b,t;

        //******核心代码******
        while(i>=0 || j>=0){
            a = i>=0 ? NumberUtil.digit(num_1_arr[i--], 10) : 0;
            b = j>=0 ? NumberUtil.digit(num_2_arr[j--], 10) : 0;
            if(a<0 || b < 0){
                throw new IllegalArgumentException("For Input number_1:"+number_1+",string_2:"+number_2);
            }

            t = carry_flag ? a+b+1 : a+b;
            if(t >= 10){
                t -=10;
                carry_flag = true;
            }else{
                carry_flag = false;
            }

            result_arr[index--] = (char)('0'+t);
        }

        //算到最后首位，如果有进位，需要补1
        if(carry_flag){
            result_arr[index] = '1';
        }
        return new String(result_arr);
    }
}
